package Algorithm.sort;

import java.util.Arrays;

//Shell类其范型T继承Comparable类中的范型<T>
//这个类又继承了Sort类,是希尔排序类
public class Shell<T extends Comparable<T>> extends Sort<T>{
    @Override
    public void sort(T[] nums) {
        int N = nums.length;//N获取数组的长度
        int h = 1;//h:随着数组长度变化的一个值,初始值是1.

        //通过N确定最大步长h(最大间隔h)
        while (h < N / 3) {//根据推算,规律如下：0<=N<6,h=1; 6<=N<15,h=4; 15<=N<42,h=13; 42<=N<123,h=40;...
            h = 3 * h + 1;//随着长度增加,递增序列h出现的值： 1,4,13,40, ...
        }

        //不断缩小步长(间隔)进行排序
        while (h>=1) {//进行一趟排序,直到步长(间隔)等于一
//          System.out.println(Arrays.toString(nums));//放开这条语句可以查看每趟排序的结果
            for (int i = h; i < N; i++) {//i:从h开始遍历,直到数组末尾,每次i+1
                for (int j=i; j>=h&&less(nums[j],nums[j-h]);j-=h) {//j:每次从i开始遍历,每次和j前面间隔h的元素比较,如果元素下标[j]<[j-h],就进行交换;完成后j-=h(j=j-h),如果交换后前面还有间隔h的元素{j>=h},就再次进行比较{less(nums[j],nums[j-h])}
                    swap(nums,j,j -h);//j和j前面间隔h的元素比较,如果数组下标[j]的元素小于数组下标[j-h],就进行交换,交换完成后如果交换后前面还有间隔h的元素{j>=h},就再次进行比较{less(nums[j],nums[j-h])}
                }
            }
            h= h/3;//h除以三向下取整,步长缩小一次再次进行排序,步长从(...,40,13,4,1)缩小到一
        }
    }
}
